/**
 * @file std_sort.inl
 * Copyright (c) 2022 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2022-10-26
 * @version : 1.0.0.0
 * @brief   : 提供各种排序算法的模板函数。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef __STD_SORT_INL__
#define __STD_SORT_INL__

#ifndef __STD_COMM_H__
#error "Please include std_comm.h before this file."
#endif // __STD_COMM_H__

////////////////////////////////////////////////////////////////////////////////

#define X_NAME_T    std

#define X_VOID_T    xstd_void_t
#define X_DIFF_T    xstd_size_t

#define X_NODE_T    xstd_size_t
#define X_NPTR_T    xstd_size_t *
#define X_ITER_T    xstd_size_t *
#define X_CTXT_T    xstd_handle_t
#define X_FCMP_T    xstd_func_compare_t

#define XCTXT_VREF(xctxt)   (xctxt)

#define XNODE_FCMP(xfcmp, xnptr_l, xnptr_r, xctxt) \
            ((xfcmp)((xnptr_l), (xnptr_r), XCTXT_VREF(xctxt)))

#define XNODE_MOVE(xnptr_l, xnptr_r, xctxt) (*(xnptr_l) = *(xnptr_r))

#define XNODE_SWAP(xnptr_l, xnptr_r, xswap, xctxt)         \
            do                                             \
            {                                              \
                XNODE_MOVE((xswap  ), (xnptr_l), (xctxt)); \
                XNODE_MOVE((xnptr_l), (xnptr_r), (xctxt)); \
                XNODE_MOVE((xnptr_r), (xswap  ), (xctxt)); \
            } while (0)

#define XNODE_INIT(xswap) \
            X_NODE_T xnode_swap = 0; (xswap) = &xnode_swap

#define XNODE_FREE(xswap)

#define XITER_EQ(xiter_l, xiter_r)    ((xiter_l) == (xiter_r))
#define XITER_UE(xiter_l, xiter_r)    ((xiter_l) != (xiter_r))
#define XITER_LT(xiter_l, xiter_r)    ((xiter_l) <  (xiter_r))
#define XITER_LE(xiter_l, xiter_r)    ((xiter_l) <= (xiter_r))
#define XITER_GT(xiter_l, xiter_r)    ((xiter_l) >  (xiter_r))
#define XITER_GE(xiter_l, xiter_r)    ((xiter_l) >= (xiter_r))
#define XITER_CP(xiter_l, xiter_r)    ((xiter_l) =  (xiter_r))

#define XITER_PREV(xiter)             (--(xiter))
#define XITER_NEXT(xiter)             (++(xiter))
#define XITER_SEEK(xiter, xoffs)      ((xiter) += (xoffs))

#define XITER_IPREV(xiter)            ((xiter) - 1)
#define XITER_INEXT(xiter)            ((xiter) + 1)
#define XITER_ISEEK(xiter, xoffs)     ((xiter) + (xoffs))

#define XITER_NREF(xiter)             (*(xiter))
#define XITER_NPTR(xiter)             (xiter)

#define XITER_DIST(xiter_b, xiter_e)  ((xiter_e) -  (xiter_b))

#define XITER_MOVE(xiter_l, xiter_r, xctxt) \
            XNODE_MOVE(XITER_NPTR(xiter_l), XITER_NPTR(xiter_r), (xctxt))

#define XITER_SWAP(xiter_l, xiter_r, xswap, xctxt) \
            XNODE_SWAP(XITER_NPTR(xiter_l), XITER_NPTR(xiter_r), (xswap), (xctxt))

#define XITER_FCMP(xfcmp, xiter_l, xiter_r, xctxt) \
            XNODE_FCMP((xfcmp), XITER_NPTR(xiter_l), XITER_NPTR(xiter_r), (xctxt))

////////////////////////////////////////////////////////////////////////////////

/**********************************************************/
/**
 * @brief 对区间 [ xiter_first, xiter_last ) 进行 插入排序。
 * 
 * @param [in ] xstdc_this  : 所属容器对象。
 * @param [in ] xnode_fcmp  : 节点 比较操作 所使用的函数。
 * @param [in ] xiter_first : 所排序区间的起始位置。
 * @param [in ] xiter_last  : 所排序区间的结束位置。
 * 
 * @return X_ITER_T : 返回结束位置的迭代器 xiter_last 。
 */
X_ITER_T X_NAME_T##_isort(
                X_CTXT_T xstdc_this,
                X_FCMP_T xnode_fcmp,
                X_ITER_T xiter_first,
                X_ITER_T xiter_last)
{
    X_ITER_T xiter_trav;
    X_ITER_T xiter_hole;
    X_ITER_T xiter_back;

    X_NPTR_T xswap_nptr;
    XNODE_INIT(xswap_nptr);

    // insertion sort [ xiter_first, xiter_last )
    if (XITER_UE(xiter_first, xiter_last))
    {
        for (XITER_CP(xiter_trav, XITER_INEXT(xiter_first));
             XITER_UE(xiter_trav, xiter_last);
             XITER_NEXT(xiter_trav))
        {
            // order next element
            XITER_CP(xiter_hole, xiter_trav);
            XNODE_MOVE(xswap_nptr, XITER_NPTR(xiter_trav), xstd_this);

            if (XNODE_FCMP(xnode_fcmp, xswap_nptr, XITER_NPTR(xiter_first), xstdc_this))
            {
                // found new earliest element, move to front
                XITER_CP(xiter_back, XITER_PREV(xiter_hole));
                while (XITER_UE(xiter_first, xiter_back))
                {
                    XITER_MOVE(xiter_hole, xiter_back, xstdc_this);
                    XITER_PREV(xiter_hole);
                    XITER_PREV(xiter_back);
                }

                XNODE_MOVE(XITER_NPTR(xiter_first), xswap_nptr, xstdc_this);
            }
            else
            {
                // look for insertion point after first
                XITER_CP(xiter_back, XITER_IPREV(xiter_hole));
                while (XNODE_FCMP(xnode_fcmp, xswap_nptr, XITER_NPTR(xiter_back), xstdc_this))
                {
                    // move hole down
                    XITER_MOVE(xiter_hole, xiter_back, xstdc_this);
                    XITER_CP(xiter_hole, xiter_back);
                    XITER_PREV(xiter_back);
                }

                // insert element in hole
                XNODE_MOVE(XITER_NPTR(xiter_hole), xswap_nptr, xstdc_this);
            }
        }
    }

    XNODE_FREE(xswap_nptr);

    return xiter_last;
}

/**********************************************************/
/**
 * @brief 
 * 对 xiter_head、xiter_vmid、xiter_tail 进行比较，
 * 交换其关联的节点数据，以实现特定顺序（升序、降序）存储。
 * 
 * @param [in ] xstdc_this : 所属容器对象。
 * @param [in ] xnode_fcmp : 节点 比较操作 所使用的函数。
 * @param [in ] xiter_head : 首位节点的迭代器。
 * @param [in ] xiter_vmid : 中间节点的迭代器。
 * @param [in ] xiter_tail : 末位节点的迭代器。
 * @param [in ] xswap_nptr : 用于交换操作的节点缓存。
 */
X_VOID_T X_NAME_T##_med3(
                X_CTXT_T xstdc_this,
                X_FCMP_T xnode_fcmp,
                X_ITER_T xiter_head,
                X_ITER_T xiter_vmid,
                X_ITER_T xiter_tail,
                X_NPTR_T xswap_nptr)
{
    if (XITER_FCMP(xnode_fcmp, xiter_vmid, xiter_head, xstdc_this))
    {
        XITER_SWAP(xiter_vmid, xiter_head, xswap_nptr, xstdc_this);
    }

    if (XITER_FCMP(xnode_fcmp, xiter_tail, xiter_vmid, xstdc_this))
    {
        XITER_SWAP(xiter_tail, xiter_vmid, xswap_nptr, xstdc_this);

        if (XITER_FCMP(xnode_fcmp, xiter_vmid, xiter_head, xstdc_this))
        {
            XITER_SWAP(xiter_vmid, xiter_head, xswap_nptr, xstdc_this);
        }
    }
}

/**********************************************************/
/**
 * @brief 
 * 快排序操作前，通过调用该接口调整排序区间 首位、中位、末位 的值，
 * 提升后续排序操作的效率。
 * 
 * @param [in ] xstdc_this : 所属容器对象。
 * @param [in ] xnode_fcmp : 节点 比较操作 所使用的函数。
 * @param [in ] xiter_head : 首位节点的迭代器。
 * @param [in ] xiter_vmid : 中位节点的迭代器。
 * @param [in ] xiter_tail : 末位节点的迭代器。
 * @param [in ] xswap_nptr : 用于交换操作的节点缓存。
 */
X_VOID_T X_NAME_T##_guess_median(
                X_CTXT_T xstdc_this,
                X_FCMP_T xnode_fcmp,
                X_ITER_T xiter_head,
                X_ITER_T xiter_vmid,
                X_ITER_T xiter_tail,
                X_NPTR_T xswap_nptr)
{
    X_DIFF_T xdiff_dist = XITER_DIST(xiter_head, xiter_tail);
    X_DIFF_T xdiff_step = 0;
    X_DIFF_T xdiff_twos = 0;

    if (xdiff_dist > 40) // Tukey's ninther
    {
        // +1 can't overflow because range was made inclusive in caller
        xdiff_step = (xdiff_dist + 1) >> 3;

        // note: intentionally discards low-order bit
        xdiff_twos = xdiff_step << 1;

        X_NAME_T##_med3(
            xstdc_this,
            xnode_fcmp,
            xiter_head,
            XITER_ISEEK(xiter_head, xdiff_step),
            XITER_ISEEK(xiter_head, xdiff_twos),
            xswap_nptr);

        X_NAME_T##_med3(
            xstdc_this,
            xnode_fcmp,
            XITER_ISEEK(xiter_vmid, -xdiff_step),
            xiter_vmid,
            XITER_ISEEK(xiter_vmid, xdiff_step),
            xswap_nptr);

        X_NAME_T##_med3(
            xstdc_this,
            xnode_fcmp,
            XITER_ISEEK(xiter_tail, -xdiff_twos),
            XITER_ISEEK(xiter_tail, -xdiff_step),
            xiter_tail,
            xswap_nptr);

        X_NAME_T##_med3(
            xstdc_this,
            xnode_fcmp,
            XITER_ISEEK(xiter_head, xdiff_step),
            xiter_vmid,
            XITER_ISEEK(xiter_tail, -xdiff_step),
            xswap_nptr);
    }
    else
    {
        X_NAME_T##_med3(
            xstdc_this,
            xnode_fcmp,
            xiter_head,
            xiter_vmid,
            xiter_tail,
            xswap_nptr);
    }
}

/**********************************************************/
/**
 * @brief 服务于 快排序操作 的分治排序操作接口。
 * 
 * @param [in ] xstdc_this  : 所属容器对象。
 * @param [in ] xnode_fcmp  : 节点 比较操作 所使用的函数。
 * @param [in ] xiter_first : 排序区间的起始节点迭代器。
 * @param [in ] xiter_last  : 排序区间的结束节点迭代器。
 * @param [in ] xswap_nptr  : 用于交换操作的节点缓存。
 * @param [out] xiter_hmid  : 操作完成后，返回的中部首位节点迭代器。
 * @param [out] xiter_tmid  : 操作完成后，返回的中部末位节点迭代器。
 */
X_VOID_T X_NAME_T##_partition(
                X_CTXT_T xstdc_this,
                X_FCMP_T xnode_fcmp,
                X_ITER_T xiter_first,
                X_ITER_T xiter_last,
                X_NPTR_T xswap_nptr,
                X_ITER_T * xiter_hmid,
                X_ITER_T * xiter_tmid)
{
    //======================================

    X_ITER_T xiter_vmid;
    X_ITER_T xiter_trav;
    X_ITER_T xiter_back;

    X_ITER_T xiter_head;
    X_ITER_T xiter_tail;

    //======================================

    XITER_CP(xiter_vmid, XITER_ISEEK(xiter_first, (XITER_DIST(xiter_first, xiter_last) >> 1)));
    XITER_CP(xiter_trav, xiter_vmid);
    XITER_CP(xiter_back, XITER_INEXT(xiter_trav));

    X_NAME_T##_guess_median(
                xstdc_this,
                xnode_fcmp,
                xiter_first,
                xiter_vmid,
                XITER_IPREV(xiter_last),
                xswap_nptr);

    //======================================

    while (XITER_LT(xiter_first, xiter_trav) &&
           !XITER_FCMP(xnode_fcmp, XITER_IPREV(xiter_trav), xiter_trav, xstdc_this) &&
           !XITER_FCMP(xnode_fcmp, xiter_trav, XITER_IPREV(xiter_trav), xstdc_this))
    {
        XITER_PREV(xiter_trav);
    }

    while (XITER_LT(xiter_back, xiter_last) &&
           !XITER_FCMP(xnode_fcmp, xiter_back, xiter_trav, xstdc_this) &&
           !XITER_FCMP(xnode_fcmp, xiter_trav, xiter_back, xstdc_this))
    {
        XITER_NEXT(xiter_back);
    }

    XITER_CP(xiter_head, xiter_back);
    XITER_CP(xiter_tail, xiter_trav);

    //======================================
    // partition

    for (;;)
    {
        //======================================

        for (; XITER_LT(xiter_head, xiter_last); XITER_NEXT(xiter_head))
        {
            if (XITER_FCMP(xnode_fcmp, xiter_trav, xiter_head, xstdc_this))
                continue;
            else if (XITER_FCMP(xnode_fcmp, xiter_head, xiter_trav, xstdc_this))
                break;
            else if (XITER_EQ(xiter_back, xiter_head))
                XITER_NEXT(xiter_back);
            else
            {
                XITER_SWAP(xiter_back, xiter_head, xswap_nptr, xstdc_this);
                XITER_NEXT(xiter_back);
            }
        }

        for (; XITER_LT(xiter_first, xiter_tail); XITER_PREV(xiter_tail))
        {
            if (XITER_FCMP(xnode_fcmp, XITER_IPREV(xiter_tail), xiter_trav, xstdc_this))
                continue;
            else if (XITER_FCMP(xnode_fcmp, xiter_trav, XITER_IPREV(xiter_tail), xstdc_this))
                break;
            else
            {
                XITER_PREV(xiter_trav);
                if (XITER_UE(xiter_trav, XITER_IPREV(xiter_tail)))
                {
                    XITER_SWAP(xiter_trav, XITER_IPREV(xiter_tail), xswap_nptr, xstdc_this);
                }
            }
        }

        if (XITER_EQ(xiter_tail, xiter_first) && XITER_EQ(xiter_head, xiter_last))
        {
            XITER_CP(*xiter_hmid, xiter_trav);
            XITER_CP(*xiter_tmid, xiter_back);
            break;
        }

        //======================================

        if (XITER_EQ(xiter_tail, xiter_first))
        {
            // no room at bottom, rotate pivot upward
            if (XITER_UE(xiter_back, xiter_head))
            {
                XITER_SWAP(xiter_trav, xiter_back, xswap_nptr, xstdc_this);
            }

            XITER_NEXT(xiter_back);
            XITER_SWAP(xiter_trav, xiter_head, xswap_nptr, xstdc_this);
            XITER_NEXT(xiter_trav);
            XITER_NEXT(xiter_head);
        }
        else if (XITER_EQ(xiter_head, xiter_last))
        {
            // no room at top, rotate pivot downward
            XITER_PREV(xiter_tail);
            XITER_PREV(xiter_trav);
            if (XITER_UE(xiter_tail, xiter_trav))
            {
                XITER_SWAP(xiter_tail, xiter_trav, xswap_nptr, xstdc_this);
            }

            XITER_PREV(xiter_back);
            XITER_SWAP(xiter_trav, xiter_back, xswap_nptr, xstdc_this);
        }
        else
        {
            XITER_PREV(xiter_tail);
            XITER_SWAP(xiter_head, xiter_tail, xswap_nptr, xstdc_this);
            XITER_NEXT(xiter_head);
        }

        //======================================
    }

    //======================================
}

/**********************************************************/
/**
 * @brief 对区间 [ xiter_first, xiter_last ) 进行快排序。
 * 
 * @param [in ] xstdc_this  : 所属容器对象。
 * @param [in ] xnode_fcmp  : 节点 比较操作 所使用的函数。
 * @param [in ] xiter_first : 排序区间的起始节点迭代器。
 * @param [in ] xiter_last  : 排序区间的结束节点迭代器。
 * @param [in ] xswap_nptr  : 用于交换操作的节点缓存。
 * @param [out] xiter_hmid  : 操作完成后，返回的中部首位节点迭代器。
 * @param [out] xiter_tmid  : 操作完成后，返回的中部末位节点迭代器。
 */
X_VOID_T X_NAME_T##_qsort(
                X_CTXT_T xstdc_this,
                X_FCMP_T xnode_fcmp,
                X_ITER_T xiter_first,
                X_ITER_T xiter_last,
                X_DIFF_T xdiff_ideal)
{
    X_ITER_T xiter_hmid;
    X_ITER_T xiter_tmid;

    X_NPTR_T xswap_nptr;
    XNODE_INIT(xswap_nptr);

    // order [ xiter_first, xiter_last )
    for (; ; )
    {
        if (XITER_DIST(xiter_first, xiter_last) <= 32)
        {
            // small
            X_NAME_T##_isort(xstdc_this, xnode_fcmp, xiter_first, xiter_last);
            break;
        }

        if (xdiff_ideal <= 0)
        {
            // heap sort if too many divisions
            _Make_heap_unchecked(xiter_first, xiter_last, _Pred);
            _Sort_heap_unchecked(xiter_first, xiter_last, _Pred);
            break;
        }

        // divide and conquer by quicksort
        X_NAME_T##_partition(
                    xstdc_this,
                    xnode_fcmp,
                    xiter_first,
                    xiter_last,
                    xswap_nptr,
                    &xiter_hmid,
                    &xiter_tmid);

        // allow 1.5 log2(N) divisions
        xdiff_ideal = (xdiff_ideal >> 1) + (xdiff_ideal >> 2);

        if (XITER_DIST(xiter_first, xiter_hmid) < XITER_DIST(xiter_tmid, xiter_last))
        {
            // loop on second half
            X_NAME_T##_qsort(xstdc_this, xnode_fcmp, xiter_first, xiter_hmid, xdiff_ideal);
            XITER_CP(xiter_first, xiter_tmid);
        }
        else
        {
            // loop on first half
            X_NAME_T##_qsort(xstdc_this, xnode_fcmp, xiter_tmid, xiter_last, xdiff_ideal);
            XITER_CP(xiter_last, xiter_hmid);
        }
    }

    XNODE_FREE(xswap_nptr);
}

////////////////////////////////////////////////////////////////////////////////

/** 使 所有相关 模板宏的定义 失效 */

////////////////////////////////////////////////////////////////////////////////

#endif // __STD_SORT_INL__
